#ifndef _memorypool_h__
#define _memorypool_h__

namespace gecko
{

	// a pool for allocating small objects
	template<typename T, int SIZE = 4>
	class MemoryPool
	{
	public:
		// constructor
		MemoryPool();

		// allocate an object from the pool
		T* Alloc();

		// free an object and return to pool
		void Free(T * memPtr);

	private:
		// structure to act as a block of memory
		struct Block
		{
			Block * Prev;
			Block * Next;
			T Data;
		};

		// allocate SIZE worth of new blocks
		void AllocateNewBlocks();

		// link all block together
		void LinkBlocks(Block * block, unsigned int numBlocks);

		// connect block to pool
		void ConnectToPool(Block * block);

		Block * m_freeBlockList;
		Block * m_inUseBlockList;
		unsigned int m_baseSize;
		unsigned int m_size;
	};

	template<typename T, int SIZE>
	MemoryPool<T, SIZE>::MemoryPool()
		: m_freeBlockList(NULL)
		, m_inUseBlockList(NULL)
		, m_baseSize(SIZE)
		, m_size(0)
	{
		AllocateNewBlocks();
	}

	template<typename T, int DEFAULT_SIZE> T* MemoryPool<T, DEFAULT_SIZE>::Alloc()
	{
		// nothing on the free list? allocate more blocks
		if (!m_freeBlockList)
		{
			AllocateNewBlocks();
		}

		// grab a free block from the head of the free list
		Block * freeBlock = m_freeBlockList;

		// unlink from free list
		m_freeBlockList = m_freeBlockList->Next;

		if (m_freeBlockList)
		{
			m_freeBlockList->Prev = NULL;
		}

		// link to in use list
		freeBlock->Next = m_inUseBlockList;

		if (m_inUseBlockList)
		{
			m_inUseBlockList->Prev = freeBlock;
		}

		// set the in use list to put to the new block
		m_inUseBlockList = freeBlock;

		// call the default constructor
		new (&freeBlock->Data) T();

		// return our memory pointer
		return &freeBlock->Data;
	}

	template<typename T, int DEFAULT_SIZE> void MemoryPool<T, DEFAULT_SIZE>::Free(T * memPtr)
	{
		// call the destructor
		memPtr->~T();
	}

	template<typename T, int SIZE> void gecko::MemoryPool<T, SIZE>::AllocateNewBlocks()
	{
		// allocate m_baseSize * blocks
		Block * newBlocks = (Block*)malloc(sizeof(Block) * m_baseSize);

		// link blocks together
		LinkBlocks(newBlocks, m_baseSize);

		// connect the new blocks to the pool
		ConnectToPool(newBlocks);

		m_size += m_baseSize;
	}

	template<typename T, int SIZE> void gecko::MemoryPool<T, SIZE>::LinkBlocks(Block * block, unsigned int numBlocks)
	{
		Block * previousBlock = NULL;

		// iterate over the number of blocks and link them to each other
		for (unsigned int i = 0; i < numBlocks; i++)
		{
			block[i].Prev = previousBlock;
			block[i].Next = (i < numBlocks - 1) ? &block[i + 1] : NULL;

			previousBlock = &block[i];
		}
	}

	template<typename T, int SIZE> void gecko::MemoryPool<T, SIZE>::ConnectToPool( Block * block )
	{
		if (!m_freeBlockList)	// pool is empty
		{
			m_freeBlockList = block;
		}
		else
		{
			Block * tailBlock = &m_freeBlockList[m_size - 1];
			tailBlock->Next = block;
			block->Prev = tailBlock;
		}
	}

}

#endif // #ifndef _memorypool_h__